package com.zk.algorithm.test;

import com.zk.algorithm.Utils;

/**
 * @author zk
 */
public class Main {

    public static void main(String...args) {
        double num = new Main().findMedianSortedArrays(new int[] {
                4,5,6
        }, new int[]{
                1,2,3
        });

        System.out.println(num);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;

        if (n % 2 == 1) {
            return findKth(nums1, nums2, 0, nums1.length - 1, 0, nums2.length - 1, n / 2 + 1);
        } else {
            double a = findKth(nums1, nums2, 0, nums1.length - 1, 0, nums2.length - 1, n / 2);
            double b = findKth(nums1, nums2, 0, nums1.length - 1, 0, nums2.length - 1, n / 2 + 1);

            return (a + b) / 2.0;
        }
    }

    private double findKth(int[] nums1, int[] nums2, int l1, int h1, int l2, int h2, int k) {
        if (l1 > h1) {
            return nums2[l2 + k - 1];
        } else if (l2 > h2) {
            return nums1[l1 + k - 1];
        }

        int m1 = l1 + ((h1 - l1) >> 1);
        int m2 = l2 + ((h2 - l2) >> 1);

        if (nums1[m1] <= nums2[m2]) {
            if (k <= (m1 - l1) + (m2 - l2) + 1) {
                return findKth(nums1, nums2, l1, h1, l2, m2 - 1, k);
            } else {
                return findKth(nums1, nums2, m1 + 1, h1, l2, h2, k - (m1 - l1 + 1));
            }
        } else {
            if (k <= (m1 - l1) + (m2 - l2) + 1) {
                return findKth(nums1, nums2, l1, m1 - 1, l2, m2, k);
            } else {
                return findKth(nums1, nums2, l1, h1, m2 + 1, h2, k - (m2 - l2 + 1));
            }
        }
    }

}
